
Namespace std

    Public Class mapheap(Of mapKey As IComparable(Of mapKey), heapKey As IComparable)
        Implements ICloneable

        Private Class heap2
            Inherits heap(Of pair(Of heapKey, mapKey))

            Public _map As map(Of mapKey, Int64) = Nothing

            Public Overrides Function [erase](ByVal index As Long) As Boolean
                debugassert(Not _map Is Nothing, "_map is nothing.")
                debugassert(Not at(index) Is Nothing, "index " + Convert.ToString(index) + " is not in heap.")
                Dim k As mapKey = Nothing
                k = at(index).second
                debugassert(MyBase.erase(index), "mybase.erase(" + Convert.ToString(index) + ") returns false.")
                If index = size() Then
                    'mybase will not call update here, if the removed index is the last one
                    debugassert(_map.erase(k), "_map.erase(" + Convert.ToString(k) + ") returns false.")
                End If

                debugassert(size() = _map.size(), "heap.size() <> _map.size()")

                Return True
            End Function

            Public Overrides Function update(ByVal index As Long, ByVal value As pair(Of heapKey, mapKey)) As Long
                debugassert(index <> npos, "should not call update with index = npos.")
                debugassert(Not value Is Nothing, "value is nothing.")
                If Not at(index) Is Nothing Then
                    debugassert(_map.erase(at(index).second) _
                                , "_map.erase(" + Convert.ToString(at(index).second) + ") returns false.")
                End If
                Dim rtn As Int64
                rtn = MyBase.update(index, value)
                debugassert(rtn <> npos, "cannot update index " + Convert.ToString(index))
                _map(value.second) = rtn

                debugassert(size() = _map.size(), "heap.size() <> _map.size()")

                Return rtn
            End Function

#If RETIRED Then
            Public Shadows Function pop_front(ByRef value As pair(Of heapKey, mapKey)) As Long
                Dim rtn As Int64
                rtn = MyBase.pop_front(value)
                debugassert(Not _map Is Nothing, "_map is nothing.")
                If Not value Is Nothing Then
                    debugassert(_map.erase(value.second) _
                                , "_map.erase(" + Convert.ToString(value.second) + ") returns false.")
                End If
                Return rtn
            End Function
#End If

            Protected Overrides Function swap(ByVal first As Int64, ByVal second As Int64) As Boolean
                debugassert(Not _map Is Nothing, "_map is nothing before swap")
                If MyBase.swap(first, second) Then
#If RETIRED Then
                    Dim it As map(Of mapKey, Int64).iterator = Nothing
                    it = _map.find(at(first).second)
                    debugassert(it <> _map.end(), "caught " + Convert.ToString(at(first).second) + " is not in map.")
                    copy((+it).second, first)

                    it = _map.find(at(second).second)
                    debugassert(it <> _map.end(), "caught " + Convert.ToString(at(second).second) + " is not in map.")
                    copy((+it).second, second)
#End If
                    _map(at(first).second) = first
                    If first <> second Then
                        _map(at(second).second) = second
                    End If
                    Return True
                Else
                    Return False
                End If
            End Function
        End Class

        Public Class iterator
            Inherits staticIterator(Of pair(Of heapKey, mapKey))

            Public Sub New()
                MyBase.New()
            End Sub

            Public Sub New(ByVal that As pointer(Of pair(Of heapKey, mapKey)))
                MyBase.New(that)
            End Sub

            Public Sub New(ByVal that As pair(Of heapKey, mapKey))
                MyBase.New(that)
            End Sub
        End Class

        Private Shared _end As iterator = Nothing
        Private _heap As heap2 = Nothing
        Private _map As map(Of mapKey, Int64) = Nothing

        Public Function begin() As iterator
            Return find(_map.begin())
        End Function

        Public Function rbegin() As iterator
            Return find(_map.rbegin())
        End Function

        Public Function [end]() As iterator
            Return _end
        End Function

        Public Function rend() As iterator
            Return _end
        End Function

        Shared Sub New()
            _end = New iterator(convertor.cast(Of pair(Of heapKey, mapKey))(Nothing))
        End Sub

        Public Sub New()
            clear()

            If isdebugmode() Then
                Dim i As heapKey = Nothing
                Dim j As heapKey = Nothing
                i = alloc(Of heapKey)()
                j = alloc(Of heapKey)()
                Try
                    selfincrease(i, j)
                Catch ex As Exception
                    raiseError("cannot add a heapKey to another, heapKey = " + GetType(heapKey).FullName _
                               + ", may cause data lost in accumulate function.", errorHandle.errorType.warning)
                End Try
            End If
        End Sub

        Public Function [erase](ByVal key As mapKey) As Boolean
            Dim heapPos As map(Of mapKey, Int64).iterator = Nothing
            heapPos = _map.find(key)
            If heapPos <> _map.end() Then
                _heap.erase((+(heapPos)).second)
#If RETIRED Then
                Dim temp As pair(Of heapKey, mapKey) = Nothing
                Dim popbackRtn As Int64
                popbackRtn = _heap.pop_back(temp)
                debugassert(popbackRtn <> npos, "_heap.pop_back(temp) returns npos.")
                If (+(heapPos)).second <> popbackRtn Then
                    _heap.update((+(heapPos)).second, temp)
                End If
                '****************************************************************************'
                If (+heapPos).second <> _heap.size() - 1 Then
                    _heap((+heapPos).second) = _heap(_heap.size() - 1)
                    debugassert(_heap.pop_back(temp) <> npos, "_heap.pop_back(temp) returns npos.")
                    If Not (_heap.empty()) Then
                        _heap.down((+heapPos).second)
                    End If
                Else
                    debugassert(_heap.pop_back(temp) <> npos, "_heap.pop_back(temp) returns npos.")
                End If
#End If
                Return True
            Else
                Return False
            End If
        End Function

        Protected Function update(ByVal key As mapKey, ByVal value As heapKey _
                                , Optional ByVal accumulate As Boolean = True) As Boolean
            Dim heapPos As map(Of mapKey, Int64).iterator = Nothing
            heapPos = _map.find(key)
            If heapPos = _map.end() Then
                Dim rtn As Int64
                rtn = _heap.insert(make_pair(value, key))
                Return rtn <> npos
            Else
                Dim heapNode As pair(Of heapKey, mapKey) = Nothing
                heapNode = _heap((+heapPos).second)
                debugassert(Not heapNode Is Nothing, "heapNode is nothing, _map is not concur with _heap.")
                If accumulate Then
                    selfincrease(heapNode.first, value)
                Else
                    copy(heapNode.first, value)
                End If
                Dim rtn As Int64
                rtn = _heap.update((+heapPos).second, heapNode)
                Return rtn <> npos
            End If
        End Function

        Public Function insert(ByVal key As mapKey, ByVal value As heapKey) As Boolean
            Return update(key, value, False)
        End Function

        Public Function accumulate(ByVal key As mapKey, ByVal value As heapKey) As Boolean
            Return update(key, value, True)
        End Function

        Public Sub pop_front(ByRef key As mapKey, ByRef value As heapKey)
            Dim heapNode As pair(Of heapKey, mapKey) = Nothing
            _heap.pop_front(heapNode)
            If Not heapNode Is Nothing Then
                key = heapNode.second
                value = heapNode.first
            Else
                key = Nothing
                value = Nothing
            End If
        End Sub

#If RETIRED Then
        Public Function pop_back(ByRef key As mapKey, ByRef value As heapKey) As Int64
            Dim rtn As Int64 = npos
            Dim heapNode As pair(Of heapKey, mapKey) = Nothing
            rtn = _heap.pop_back(heapNode)
            If rtn <> npos Then
                key = heapNode.second
                value = heapNode.first
            End If
            Return rtn
        End Function
#End If

        Private Function find(ByVal it As map(Of mapKey, Int64).iterator) As iterator
            If it Is Nothing OrElse it = _map.end() Then
                Return [end]()
            Else
                Dim heapnode As pair(Of heapKey, mapKey) = Nothing
                debugassert(_heap.take((+it).second, heapnode) _
                            , "cannot get _heap(" + Convert.ToString((+it).second) + ")")
                Return New iterator(heapnode)
            End If
        End Function

        Public Function find(ByVal key As mapKey) As iterator
            Return find(_map.find(key))
        End Function

        Public Sub clear()
            If _map Is Nothing Then
                _map = New map(Of mapKey, Int64)
            Else
                _map.clear()
            End If
            If _heap Is Nothing Then
                _heap = New heap2
            Else
                _heap.clear()
            End If
            _heap._map = _map
        End Sub

        Public Function size() As Int64
            debugassert(_heap.size() = _map.size(), "_heap.size() <> _map.size()")
            Return _heap.size()
        End Function

        Public Function empty() As Boolean
            debugassert(_heap.empty() = _map.empty(), "_heap.empty() <> _map.empty()")
            Return _heap.empty()
        End Function

        Public Overrides Function ToString() As String
            Return Convert.ToString(_heap) + newline.incode() + Convert.ToString(_map)
        End Function

        Public Function Clone() As Object Implements System.ICloneable.Clone
            Dim rtn As mapheap(Of mapKey, heapKey) = Nothing
            rtn = New mapheap(Of mapKey, heapKey)()

            copy(rtn._heap, _heap)
            copy(rtn._map, _map)
            rtn._heap._map = rtn._map

            Return rtn
        End Function

        Private Class unittestInfo
            Public mapheap As mapheap(Of mapKey, heapKey) = Nothing
            Public keys As vector(Of mapKey) = Nothing

            Public Sub New()
                mapheap = New mapheap(Of mapKey, heapKey)()
                keys = New vector(Of mapKey)()
            End Sub
        End Class

        Private Class unittestActions
            Private Shared Sub parseParameter(ByVal obj As Object _
                                              , ByRef mapheap As mapheap(Of String, String) _
                                              , ByRef keys As vector(Of String))
                Dim info As mapheap(Of String, String).unittestInfo = Nothing
                info = convertor.cast(Of mapheap(Of String, String).unittestInfo)(obj)
                mapheap = info.mapheap
                keys = info.keys

                assert(Not mapheap Is Nothing, "mapheap is nothing.")
                assert(Not keys Is Nothing, "keys is nothing.")
            End Sub

            Public Shared Sub insert(ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, mapheap, keys)

                Dim s As String = Nothing
                s = strleft(createGUID(), 5)
                Dim n As Double
                n = rnd(0, 1000)
                raiseError("insert " + s + ", " + Convert.ToString(n))
                assert(mapheap.insert(s, n) _
                            , "mapheap.insert(" + s + ", " + Convert.ToString(n) + ") returns false.")
                If keys.find(s) = npos Then
                    keys.push_back(s)
                End If
            End Sub

            Public Shared Sub accumulate(ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, mapheap, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    Dim n As Double
                    n = rnd(0, 1000)
                    raiseError("accumulate " + keys(i) + ", " + Convert.ToString(n))
                    assert(mapheap.accumulate(keys(i), n) _
                                , "mapheap.accumulate(" + keys(i) + ", " _
                                + Convert.ToString(n) + ") returns false.")
                End If
            End Sub

            Public Shared Sub pop_front(ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, mapheap, keys)

                If Not mapheap.empty() Then
                    Dim s As String = Nothing
                    mapheap.pop_front(s, Nothing)
                    assert(Not isemptystring(s), "mapheap.pop_front() failed.")
                    raiseError("pop_front " + s)
                    Dim i As Int64
                    i = keys.find(s)
                    assert(i <> npos, "j=npos")
                    keys.erase(i)
                End If
            End Sub

            Public Shared Sub find(ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, mapheap, keys)

                If Not keys.empty() Then
                    Dim i As Int64
                    i = rnd(0, keys.size(), True)
                    assert(mapheap.find(keys(i)) <> mapheap.end(), "mapheap.find(" + keys(i) + ") failed.")
                    raiseError("find " + keys(i))
                End If
            End Sub

            Public Shared Sub [erase](ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, mapheap, keys)

                If Not keys.empty() Then
                    Dim j As Int64
                    j = rnd(0, keys.size(), True)
                    raiseError("remove " + keys(j))
                    assert(mapheap.erase(keys(j)), "mapheap.erase(" + keys(j) + ") returns false.")
                    keys.erase(j)
                End If
            End Sub

            Public Shared Sub clone(ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                parseParameter(obj, mapheap, Nothing)

                Dim info As mapheap(Of String, String).unittestInfo = Nothing
                info = convertor.cast(Of mapheap(Of String, String).unittestInfo)(obj)
                Dim oldmapheap As mapheap(Of String, String) = Nothing
                oldmapheap = info.mapheap
                info.mapheap = Nothing
                copy(info.mapheap, mapheap)
                assert(Not Object.ReferenceEquals(info.mapheap, oldmapheap), "cannot clone to a new instance.")
                assert(compare(info.mapheap._heap, oldmapheap._heap) = 0, "info.mapheap._heap <> oldmapheap._heap.")
                raiseError("clone a same instance with existing one.")
            End Sub

            Public Shared Sub clear(ByVal obj As Object)
                Dim mapheap As mapheap(Of String, String) = Nothing
                Dim keys As vector(Of String) = Nothing
                parseParameter(obj, mapheap, keys)

                raiseError("clear")
                mapheap.clear()
                assert(mapheap.size() = 0, "mapheap.size()<>0 after clear.")
                keys.clear()
            End Sub
        End Class

        Public Shared Sub automaticalUnittest()
            Dim roundcount As Int64 = 10240
            If isreleasebuild() Then
                roundcount *= 20
            End If

            raiseError("******** automatical mapheap unitTest *******", errorHandle.errorType.application)

            Dim info As mapheap(Of String, String).unittestInfo = Nothing
            info = New mapheap(Of String, String).unittestInfo()
            randomrun.invoke(roundcount, info _
                             , New randomrun.info(0.33, AddressOf unittestActions.insert) _
                             , New randomrun.info(0.3, AddressOf unittestActions.accumulate) _
                             , New randomrun.info(0.1, AddressOf unittestActions.pop_front) _
                             , New randomrun.info(0.12, AddressOf unittestActions.find) _
                             , New randomrun.info(0.1, AddressOf unittestActions.erase) _
                             , New randomrun.info(0.01, AddressOf unittestActions.clone) _
                             , New randomrun.info(0.04, AddressOf unittestActions.clear))

            While Not info.mapheap.empty()
                unittestActions.pop_front(info)
            End While

            raiseError("******** finish automatical unittest ********", errorHandle.errorType.application)
        End Sub

        Public Shared Sub unittest()
            Console.WriteLine("******** mapheapUnitTest *******")

            Dim firstRound As Boolean = True

            Dim _mapheap As mapheap(Of String, Double) = Nothing
            Dim _mapheap2 As mapheap(Of String, Double) = Nothing
            _mapheap = New mapheap(Of String, Double)
            _mapheap2 = New mapheap(Of String, Double)
            Dim key As String = Nothing
            Dim value As Double = 0
retry:
            If firstRound Then
                Console.WriteLine("will use accumulate now.")
            Else
                Console.WriteLine("will use insert now.")
            End If
            Console.Write("input key string ")
            key = Console.ReadLine
            While Not key Is Nothing
                Dim str As String = Nothing
                Do
                    Console.Write("input value double ")
                    str = Console.ReadLine
                Loop Until convertor.todouble(str, value)
                If firstRound Then
                    _mapheap.accumulate(key, value)
                    _mapheap2.accumulate(key, value)
                Else
                    _mapheap.insert(key, value)
                    _mapheap2.insert(key, value)
                End If
                Console.Write("input key string ")
                key = Console.ReadLine
            End While

            If firstRound Then
                Console.WriteLine("will use insert now.")
            Else
                Console.WriteLine("will use accumulate now.")
            End If
            Console.Write("input key string ")
            key = Console.ReadLine
            While Not key Is Nothing
                Dim str As String = Nothing
                Do
                    Console.Write("input value double ")
                    str = Console.ReadLine
                Loop Until convertor.todouble(str, value)
                If firstRound Then
                    _mapheap.insert(key, value)
                    _mapheap2.insert(key, value)
                Else
                    _mapheap.accumulate(key, value)
                    _mapheap2.accumulate(key, value)
                End If
                Console.Write("input key string ")
                key = Console.ReadLine
            End While

            Console.WriteLine("will use erase now.")
            Console.Write("input key string ")
            key = Console.ReadLine
            While Not key Is Nothing
                _mapheap.erase(key)
                _mapheap2.erase(key)
                Console.Write("input key string ")
                key = Console.ReadLine
            End While

            Console.WriteLine("mapheap.size() = " + Convert.ToString(_mapheap.size()))
            Console.WriteLine("mapheap.empty() = " + Convert.ToString(_mapheap.empty()))
            Console.WriteLine("output each element with pop_front method.")
            _mapheap.pop_front(key, value)
            While Not isemptystring(key)
                Console.WriteLine(key + character.tab + Convert.ToString(value))
                _mapheap.pop_front(key, value)
            End While

            'Console.WriteLine("output each element with pop_back method.")
            'While _mapheap2.pop_back(key, value) <> npos
            '    Console.WriteLine(key + character.tab + Convert.ToString(value))
            'End While

            If firstRound Then
                firstRound = False
                Console.WriteLine("using clear method, and do again.")
                _mapheap.clear()
                _mapheap2.clear()
                GoTo retry
            End If
            Console.WriteLine("********************************")
        End Sub
    End Class
End Namespace
